package cnki.kg.algorithm;

import com.alibaba.fastjson.JSON;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class BinarySearch {
    @Test
    public void TestBinarySearch() {
        int[] arr = new int[]{1, 4, 7, 2, 5, 8, 3, 6, 9};
        Arrays.sort(arr);
        int index = binarySearch(arr, 9);
        System.out.println(index);
    }

    private int binarySearch(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = Math.round((left + right) / 2);
            int guess = arr[mid];
            if (guess == num) {
                return mid;
            }
            if (guess > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    @Test
    public void TestIsPerfectSquare() {
        boolean result = isPerfectSquare(2000105819);
    }

    /**
     * 完美平方数
     *
     * @param num
     * @return
     */
    private boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }
        int count = 0;
        int left = 2;
        int right = num - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int guerssSquare = mid * mid;
            if (guerssSquare == num) {
                return true;
            }
            if (guerssSquare > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            count++;
            System.out.println("第" + count + "次查找");
        }
        return false;
    }

    private boolean isPerfectSquare3(int num) {
        if (num < 2) {
            return true;
        }
        int count = 0;
        int left = 2;
        int right = num / 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            int guerssSquare = mid * mid;
            if (guerssSquare == num) {
                return true;
            }
            if (guerssSquare > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            count++;
            System.out.println("第" + count + "次查找");
        }
        return false;
    }

    private boolean isPerfectSquare2(int num) {
        if (num < 2) {
            return true;
        }
        long left = 2;
        long right = num / 2;
        long mid;
        long guessSquared;
        while (left <= right) {
            mid = left + (right - left) / 2;
            guessSquared = mid * mid;
            if (guessSquared == num) {
                return true;
            }
            if (guessSquared > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

    @Test
    public void mySqrt2() {
        int res = -1;
        int x = 2147395599;
        if (x == 0) res = 0;
        if (x == 1) res = 1;
        int left = 1;
        int right = x - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            double xxx = Math.pow(mid, 2);
            if (xxx <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(res);
    }

    @Test
    public void mySqrt() {
        int res = -1;
        int x = 2147395599;
        if (x == 0) res = 0;
        if (x == 1) res = 1;
        int left = 1;
        int right = x - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //long val=(mid << mid);
            long val = Long.parseLong(multiply(String.valueOf(mid), String.valueOf(mid)));
            if (val <= x) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(res);
    }

    //定义方法multiply的功能
    public String multiply(String str1, String str2) {
        int[] num1 = new int[str1.length()];
        int[] num2 = new int[str2.length()];
        int[] result = new int[str1.length() + str2.length()];
        //将两个字符串转成整型数组，顺序转换，数组下标越小，数字对应的位数越高
        for (int i = 0; i < str1.length(); i++) {
            num1[i] = Integer.parseInt(str1.substring(i, i + 1));
        }
        for (int i = 0; i < str2.length(); i++) {
            num2[i] = Integer.parseInt(str2.substring(i, i + 1));
        }

        //两大数相乘
        for (int a = 0; a < str1.length(); a++) {
            for (int b = 0; b < str2.length(); b++) {
                result[a + b] += num1[a] * num2[b];
            }
        }

        ////判断是否需要进位，满10进1,因为存储顺序与位数高低相反，所以采用逆序进位
        int temp;
        for (int k = result.length - 1; k > 0; k--) {
            temp = result[k] / 10;  //数组下标大的向数组下标小的进位
            result[k - 1] += temp;
            result[k] = result[k] % 10;
        }

        //将结果数组逆序转化为字符串
        String resultstr = "";
        for (int i = 0; i < result.length - 1; i++) {
            resultstr += "" + result[i];
        }

        return resultstr;
    }

    @Test
    public void reversePrint() {
        //reverseList();
    }

    @Test
    public void replaceSpace() {
        String s = reverseLeftWords("lrloseumgh", 6);
    }

    public String reverseLeftWords(String s, int n) {
        if (s == null || s == "") return "";
        char[] chars = s.toCharArray();
        String left = "";
        String right = "";
        for (int i = 0; i < chars.length; i++) {
            if (n > i) {
                left += String.valueOf(chars[i]);
            } else {
                right += String.valueOf(chars[i]);
            }
        }
        return right + left;
    }

    @Test
    public void Sequence() {
        //int[][] continuousSequence = findContinuousSequence(9);
        int[][] continuousSequence2 = getsidebar(9);
        System.out.println(JSON.toJSONString(continuousSequence2));
    }

    private int[][] findContinuousSequence(int target) {
        int i = 1; // 滑动窗口的左边界
        int j = 1; // 滑动窗口的右边界
        int sum = 0; // 滑动窗口中数字的和
        List<int[]> res = new ArrayList<>();

        while (i <= target / 2) {
            if (sum < target) {
                // 右边界向右移动
                sum += j;
                j++;
            } else if (sum > target) {
                // 左边界向右移动
                sum -= i;
                i++;
            } else {
                // 记录结果
                int[] arr = new int[j - i];
                for (int k = i; k < j; k++) {
                    arr[k - i] = k;
                }
                res.add(arr);
                // 左边界向右移动
                sum -= i;
                i++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }

    private int[][] getsidebar(int target) {
        int left = 1;
        int right = 1;
        int sum = 0;
        List<int[]> res = new ArrayList<>();
        while (left <= target / 2) {
            if (sum < target) {
                sum += right;
                right++;
            } else if (sum > target) {
                sum -= left;
                left++;
            } else {
                int[] arr = new int[right - left];
                for (int j = left; j < right; j++) {
                    arr[j - left] = j;
                }
                res.add(arr);
                sum -= left;
                left++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    public int movingCount(int m, int n, int k) {
        int[][] arr = new int[m - 1][n - 1];
        for (int[] ints : arr) {

        }
        return 0;
    }
}
